1. Field of the Invention
The present invention is directed to a mechanism for providing concurrent operations in order to maximize processor use, particularly in a compiled object oriented paradigm such as C++.
2. Description of the Related Art
In a simplistic model (such as an isolated workstation) a single program running on a single processor would perform each of its routines in a programmed order in sequence, dominating the processor until complete. A call to a subroutine (possibly a program module stored in a separate area of memory) would cause the processor to suspend or block operation on the main program while processing the subroutine. In this scenario, the processor resources are completely utilized (the processor is never left idle) and as there are no concurrent programs competing for the processor resources, the domination of the processor for the duration of processing the program and its routines is not a problem.
In a distributed system, multiple processors each with associated memory are available, and a call to a subroutine outside the program could easily be a call to a program module residing on a different processor on the system. It is the remote processor then that would perform the operations for the subroutine to return the desired results to the main program.
Linked multiple processors or distributed systems are becoming increasingly popular with the advent of the distributed computing environment (DCE) of the Open System Foundation (OSF), an emerging technology enabling distributed computing among heterogenous systems.
In the normal local procedure call, there is a unique interface between the calling program and a specific subroutine, and the local procedure call invokes all necessary logic for operability. When the subroutine resides on a different machine than the calling program, as in a distributed system, communications logic (i.e. the location of the subroutine, data conversions, etc.) is required for the call and traditionally must be hard coded into the calling and/or called programs. This would be especially complex where the remote processor is not homogeneous or compatible with the calling function.
By contrast, DCE, when implemented on each of the disparate systems, allows transparent inter-operation between computers on the network through a mechanism called the "remote procedure call" (RPC) that extends to the distributed environment, and particularly the heterogeneous environment, the concept of the local procedure call.
As a result, remote calls are handled transparently to the programmer as well as the user, as the programmer is no longer required to code support for each remote call.
However, in any distributed environment, unless provisions are made during program planning, the main program continues to occupy its processor even while suspended or blocked and awaiting return of its remote call. During the period of this suspension, the processor is idle.
The time that the waiting program is suspended might, in real terms, amount to only fractions of a second if the remote processor can operate on the subroutine immediately. However, in complex distributed systems, queuing at the remote processor can introduce considerable time delays, and all the while the waiting processor continues to be idle.
The ideal situation would be to have concurrent operations on each processor, that is, every active object would have a separate thread so that while one thread was "waiting" or suspended, other threads could use the processor.
DCE (and other systems) include features that permit the programmer to create and manipulate multiple threads in a single program. In DCE, this multi-threading feature is in the form of an application programming interface based on the "pthreads" interface, specified by POSIX in their 1003.4a Standard (Draft 4): IEEE P1003.4a/D4 Draft Standard, Threads Extension for Portable Operating Systems, Technical Committee on Operating Systems of the Institute of Electrical and Electronic Engineers (IEEE) Computer Society, New York, U.S.A., Aug. 10, 1990.
However, DCE and other multithreading systems require the programmer to structure a program with multiple threads of control, and this can introduce increasing complexity in designing the program. The numerous threads must be managed, scheduled and allowed to communicate in a controlled manner, and it is usually difficult to foresee all occasions in which concurrency would be appropriate, particularly if lengthy thread extensions are caused by factors at remote processors during remote calls.
Thus, multi-threading features tend to be inhibiting to use and problems are difficult to predict.
In addition, there is a cost associated with switching threads in the processor of the waiting thread, in saving and reloading the processor registers, and in making the appropriate stack adjustments for the new thread. Consequently, the number of planned control switches between threads in a processor should be minimized in a traditional multi-threading system in order to truly maximize the economic benefit of concurrency.
The solution proposed in non-object oriented systems and in some object oriented systems with extended compilers, for example COOL (R. Chandra, A. Gupta and J. Hennessy, "COOL: A Language for Parallel Programming", Languages and Compilers for Parallel Computing, Editors D. Gelernter, A. Nicolau and D. Padua, MIT Press, 1990), is a mechanism known as a "future result". When a remote call is issued, the result of the subroutine call is stored in a future object or type to be returned to the main program in response to a future procedure call. In this way, the main program continues to run on its processor while the subroutine runs concurrently or synchronously. If the main program comes to the "future" call before the future variable is available, the program simply blocks at that point to await the desired result.
In non-object oriented systems, the message that the user is implementing a synchronous invocation varies widely from language to language. Explicit functions, such as calling "resolve" with "future" as an argument might be required in some systems, while in other systems the "future" call is handled automatically.
Object oriented environments seem particularly well suited to use through remote calls and remote procedure calls because the conception and implementation of object oriented languages provides the tools and facilities for modular programming in code sharing.
The computer simulated "objects" in object oriented paradigms are defined and maintained independently of each other, the definition of an object including its "methods", (that is the procedures or operations the object is capable of performing), and its variables (that is, its attributes, the values of which can change over time). Objects are defined through class definitions. A class is a template that defines the methods and variables to be included in a particular type of object. Classes can be defined in terms of other classes, that is the characteristics (methods and/or variables) of a subclass can be inherited from a superior, more generalized base class. In addition to the methods and variables they inherit, subclasses define their own methods and variables and this may include characteristics permitting the override of inherited characteristics, although the implementation of such derived classes is visible only within the class to prevent contamination of other class implementations.
An abstract class is a base class with no objects or instances, the sole purpose of which is to organize a class hierarchy or to find methods or variables that will apply to a lower level inherited class. Yet inherited methods and variables can be more narrowly defined or even redefined in a derived class, so that objects defined through this technology can be highly specialized and can fit within a complex system of related but not identical objects, and class hierarchies can encompass many levels. The flexibility available through object oriented technology is certainly attractive in the promise of breadth it can add in distributed computing environments.
However, the most popular object oriented language, C++ for example, is an inherently sequential language without any provision for concurrency. In fact, concurrent programming operations have been difficult to implement in object oriented paradigms in general, due to a lack of proper support for concurrency control, synchronization and mutual exclusions.
Futures have been used in object oriented languages others than C++ (such as LISP, Concurrent SmallTalk and COOL), however previous attempts to introduce them into C++ have been syntactically clumsy, for example requiring a programmer to add prologue and epilogue code in the program to specifically deal with the futures, or have required an extension of the language or non-standard compiler modification.
Numerous attempts have also been made in adding concurrency to C++, employing one of two approaches. In the first approach, the language is extended and new language constructs are added to handle the creation and control of concurrency, that is, the compiler is extended to recognize the new language constructs. A common way used by these languages to add concurrency is to encapsulate concurrency creation, synchronization and mutual exclusion at the object level. Such an object is called "active". While such newer extended languages provide enhanced performance, higher level constructs, and compile time checking, they are limited by a lack of portability between operating systems.
The second approach employs a library of reusable abstractions that encapsulate the lower level details of concurrency (for example, architecture, data partitions, communication and synchronization). The library approach keeps the concurrency mechanisms outside of the language, allowing the programmer to work with familiar compilers and tools, and this supports a higher level of portability, while providing the option of supporting many concurrent models through a variety of libraries. However, while most present concurrent task libraries for C++ attempt to provide concurrency through "active" objects, they fail to provide implicit concurrency and they also impose unwieldy restrictions on users. For example, the task library described in T. W. Doeppner, Jr. et al: "C++ on a Parallel Machine", Report CS-87-26, Department of Computer Science, Brown University, November 1987, is one of the earliest C++ libraries providing true concurrency. However, thread management is explicit (proper management is imposed on the programmer) and only one level of subclassing is permitted (limiting the flexibility obtainable through multiple inheritance levels available in object oriented languages). Limiting the number of inheritance levels to one is similar to the approach taken in the class library described in AT&T's C++ Language System Release 2.0, Product Reference Manual, 1989, Select Code 307-146. The library described in D. Grunwald's "A Users Guide to AWESIME: An Object Oriented Parallel Programming and Simulation Systems", Technical Report CU-CS-552-91, Department of Computer Science, University of Colorado at Boulder, permits arbitrary levels of subclassing from the task class in the library called "thread", but thread management using this class library is again explicit. In the numerous attempts at solving the problem of concurrency in C++ through a class library, the issues of object distribution over a network, asynchronous invocation and future communication, are not addressed.